﻿// 0831train01.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <limits>
#include <vector>
#include <unordered_map>
#include <unordered_set>

using namespace std;

/*
 要求将这些货币全部换算成人民币分（fen）后进行汇总，汇总结果仅保留整数，小数部分舍弃
元和分的换算关系都是1:100，如下：

1CNY=100fen（1元=100分）
1HKD=100cents（1港元=100港分）
1JPY=100sen（1日元=100仙）
1EUR=100eurocents（1欧元=100欧分）
1GBP=100pence（1英镑=100便士）
汇率表如下：
即：100CNY = 1825JPY = 123HKD = 14EUR = 12GBP

CNY	JPY	 HKD	EUR	GBP
100	1825 123	14	12

输入描述
第一行输入为N，N表示记录数。0<N<100
之后N行，每行表示一条货币记录，且该行只会是一种货币

输出描述
将每行货币转换成人民币分（fen）后汇总求和，只保留整数部分
输出格式只有整数数字，不带小数，不带单位

输入
2
20CNY53fen
53HKD87cents
输出
6432
 */

class Solution01
{
public:
    bool isNum(char oh_char)
    {
        return oh_char >= '0' && oh_char <= '9';
    }

    void updateResult(vector<double>&num_vec, vector<string>&kind_vec)
    {
        result += changeNum(num_vec[0], kind_vec[0]);

        if (num_vec.size()==2)
        {
            result += changeNum(num_vec[1], kind_vec[1]);
        }
        //updateResult
    }

    Solution01(vector<string>&str_vec)
    {
        for (auto&oh_str:str_vec)
        {
            double curr_num = 0;
            string curr_kind;

            vector<double>num_vec;
            vector<string>kind_vec;
            for (auto&oh_char:oh_str)
            {
	            //vector推完重置标志位
                if (isNum(oh_char))
                {
                    curr_num = curr_num * 10 + (oh_char - '0');

                    if (!curr_kind.empty())
                    {
                        kind_vec.push_back(curr_kind);
                        curr_kind = "";
                    }
                }
                else
                {
                    if (curr_num!=0)
                    {
                        num_vec.push_back(curr_num);
                        curr_num = 0;
                    }
                    curr_kind += oh_char;
                }

                //for (auto&oh_char
                //------
            }
            if (!curr_kind.empty())
            {
                kind_vec.push_back(curr_kind);
                curr_kind = "";
            }

            updateResult(num_vec, kind_vec);
        }

        cout << int(result);
        //Solution01
    }
private:
    double result = 0;
    double changeNum(double&num, string&kind)
    {
/*
CNY	JPY	 HKD	EUR	GBP
100	1825 123	14	12
*/
        if (kind=="CNY")
        return num * 100;

        if (kind == "HKD")
            return num * 100 / 123 * 100;

        if (kind == "JPY")
            return num * 100 / 1825 * 100;

        if (kind == "EUR")
            return num * 100 / 14 * 100;

        if (kind == "GBP")
            return num * 100 / 12 * 100;
/*
1CNY=100fen（1元=100分）
1HKD=100cents（1港元=100港分）
1JPY=100sen（1日元=100仙）
1EUR=100eurocents（1欧元=100欧分）
1GBP=100pence（1英镑=100便士）
*/
        if (kind == "fen")
            return num;

        if (kind == "cents")
            return num * 100 / 123;

        if (kind == "sen")
            return num * 100 / 1825;

        if (kind == "eurocents")
            return num * 100 / 14;

        if (kind == "pence")
            return num * 100 / 12;


        //changeNum
    }
};


/*
输入为3行
第一行：充电设备个数n
第二行：每个充电设备的输出功率
第三行：充电站最大输出功率p_max

输出描述
功率集合P的最优元素
补充说明：
1. 充电设备个数n > 0
2. 最优元素必须小于或等于充电站最大输出功率p_max

输入
3
1 2 3
5
输出
5
 */
class Solution02
{
public:
    Solution02(vector<int>&num_vec, int amount)
    {
        vector<bool>dynamic_vec(amount + 1, false);

        dynamic_vec[0] = true;

        for (auto& curr : num_vec)
        {
            for (int dp_amount = amount; dp_amount >=0; dp_amount--)
            {
                if (dp_amount - curr < 0) continue;

                //能凑出dp_amount-curr，一定能凑出dp_amount
                if (dynamic_vec[dp_amount - curr])
                {
                    dynamic_vec[dp_amount] = true;
                }
            }

            //for (int i=0; i<=amount; i++)
            //{
            //    if (dynamic_vec[i])
            //    {
            //        cout << i << ' ';
            //    }
            //}
            //cout << '\n';
        }

        int result = 0;
        for (int num=amount; num>=0; num--)
        {
	        if (dynamic_vec[num])
	        {
                result = num;
                break;
	        }
        }
        cout << result;
        //Solution02
    }
};


/*
 给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1
你可以认为每种硬币的数量是无限的

示例 1
输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1
 */
class Solution03
{
public:
    int coinChange(vector<int>& coins, int amount) {

        vector<int>dynamic_vec(amount + 1, amount+1);

        //凑出0最少需要0个硬币
        dynamic_vec[0] = 0;

        for (auto& coin : coins)
        {
            for (int dp_amount = 0; dp_amount <= amount; dp_amount++)
            {
                if (dp_amount - coin < 0) continue;

	            //dynamic_vec[dp_amount-coin]+1
                dynamic_vec[dp_amount] = min(dynamic_vec[dp_amount], dynamic_vec[dp_amount - coin] + 1);
            }

            for (auto&num:dynamic_vec)
            {
                cout << num << ' ';
            }
            cout << '\n';
            
        }

        if (dynamic_vec[amount] == amount + 1) return -1;

        return dynamic_vec[amount];

        //coinChange
    }
};


/*
 已知该软盘容量为1474560字节。文件占用的软盘空间都是按块分配的，每个块大小为512个字节
 一个块只能被一个文件使用
 拷贝到软盘中的文件必须是完整的

输入描述
第1行为一个整数N，表示计算机中的文件数量。1 ≤ N ≤ 1000
接下来的第2行到第N+1行(共N行)，每行为一个整数，表示每个文件的大小Si，单位为字节

输出描述
科学家最多能拷贝的文件总大小

输入
3
737270
737272
737288
输出
1474542

3个文件中，每个文件实际占用的大小分别为737280字节、737280字节、737792字节
只能选取前两个文件，总大小为1474542字节
后两个文件总大小更大且未超过1474560字节，因为实际占用的大小超过了1474560字节，所以不能选后两个文件
 */

class Solution04
{
public:
    Solution04(vector<double>&num_vec)
    {
        int v_size = num_vec.size();
        vector<int>block_vec(v_size);
        for (int i=0; i<v_size; i++)
        {
            block_vec[i] = ceil(num_vec[i] / 512);
        }

        //dp[i][w]=dp[i-1][w]+dp[i][w-curr_w]+curr_value
        //dp[amount] = dp[amount-curr]+num_vec[curr]
        vector<int>dynamic_vec(total + 1);
        for (int i=0; i<v_size; i++)
        {
            int curr_block = block_vec[i];
            for (int dp_block=total; dp_block >=0; dp_block--)
            {
                if (dp_block - curr_block < 0) continue;

                int choose_curr = dynamic_vec[dp_block - curr_block] + num_vec[i];
                dynamic_vec[dp_block] = max(dynamic_vec[dp_block], choose_curr);
            }
        }

        int result = 0;
        for (int num=total; num>=0; num--)
        {
	        if (dynamic_vec[num]!=0)
	        {
                result = dynamic_vec[num];
	        	break;
	        }
        }
        cout << result;
        //Solution04
    }
private:
    int total = 1474560 / 512;
};


/*
 从n个数中选若干（至少1）个数求和，求所有方案中第k小的和（和相同但取法不同的视为不同方案）
对于所有数据，1 <= k < 2^n， n个正整数每个都不超过10^9
输入描述
第一行输入2个正整数n, k
第二行输入这n个正整数

输出描述
输出第k小的和

输入
5 12
1 2 3 5 8
输出
8

前12小的和分别为: 1 2 3 3 4 5 5 6 6 7 8 8
 */
class Solution05
{
public:
    Solution05(vector<int>&num_vec, int k)
    {
        int total_sum = 0;
        int v_size = num_vec.size();
        for (int i=0; i<v_size; i++)
        {
            total_sum += num_vec[i];
        }

        vector<int>dynamic_vec(total_sum + 1);
        dynamic_vec[0] = 1; //和为0,1种取法

        for (auto&curr:num_vec)
        {
            for (int dp_sum=total_sum; dp_sum>=0; dp_sum--)
            {
                if (dp_sum - curr < 0) continue;

                dynamic_vec[dp_sum] += dynamic_vec[dp_sum - curr];
            }
        }

        int count = 0;
        //0不能算进去
        for (int i=1;i<=total_sum; i++)
        {
            count += dynamic_vec[i];
            if (count>= k)
            {
                cout << i;
                break;
            }
        }

        //Solution05
    }
};

int main()
{
	{
/*
5 12
1 2 3 5 8
 */
        int v_size, k;
        cin >> v_size >> k;

        vector<int>num_vec(v_size);
        for (int i=0; i<v_size; i++)
        {
            cin >> num_vec[i];
        }

        Solution05 solu(num_vec, k);

        return 0;
	}
	{
        int v_size;
        cin >> v_size;

        vector<double>num_vec(v_size);
        for (int i=0; i<v_size; i++)
        {
            cin >> num_vec[i];
        }

        Solution04 solu(num_vec);

        return 0;
	}
	{
/*
3
1 2 3
5
*/
        int v_size;
        cin >> v_size;
        vector<int>num_vec(v_size);

        for (int i=0; i<v_size; i++)
        {
            cin >> num_vec[i];
        }

        int amount;
        cin >> amount;

        Solution02 solu(num_vec, amount);

        return 0;
	}
	{
        vector<int>coins = { 1, 2, 5 };
        int amount = 11;

        Solution03 solu;
        cout << solu.coinChange(coins, amount);

        return 0;
	}
    int v_size;
    cin >> v_size;
    vector<string>str_vec(v_size);

    for (int i=0; i<v_size; i++)
    {
        cin >> str_vec[i];
    }

    Solution01 solu(str_vec);


}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
